//
//  红黑树简介.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/18.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
/**
 红黑树是一种近似平衡的二叉搜索树，它能确保任何一个节点的左右子树的高度差小于两倍
 1. 每个节点要么是红色，要么是黑色
 2. 根节点是黑色
 3. 每个叶子节点都是黑色
 4. 不能有相邻的两个红色节点
 5. 从任意一个节点到其每个叶子的所有路径都包含相同数目的黑色节点
 */
/**
 AVL 提供更快的查询(完全平衡)
 红黑树 提供更快的添加与插入(近似平衡)
 AVL 需要更多的内存空间
 红黑树常常用开发库里的在Map,Set里；
 */
